/*
 * @lc app=leetcode.cn id=394 lang=cpp
 * @lcpr version=30204
 *
 * [394] 字符串解码
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack; // 存储重复次数
        stack<string> stringStack; // 存储当前字符串
        string currentString = ""; // 当前处理的字符串
        int k = 0; // 当前解析的数字

        for (char c : s) {
            if (isdigit(c)) {
                // 解析数字
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                // 遇到 '['，将当前数字和字符串入栈
                countStack.push(k);
                stringStack.push(currentString);
                // 重置当前数字和字符串
                k = 0;
                currentString = "";
            } else if (c == ']') {
                // 遇到 ']'，弹出栈顶的数字和字符串
                int repeatCount = countStack.top();
                countStack.pop();
                string decodedString = stringStack.top();
                stringStack.pop();
                // 生成重复的字符串
                for (int i = 0; i < repeatCount; ++i) {
                    decodedString += currentString;
                }
                // 更新当前字符串
                currentString = decodedString;
            } else {
                // 普通字符，直接拼接到当前字符串
                currentString += c;
            }
        }

        return currentString;
    }
};
// @lc code=end



/*
// @lcpr case=start
// "3[a]2[bc]"\n
// @lcpr case=end

// @lcpr case=start
// "3[a2[c]]"\n
// @lcpr case=end

// @lcpr case=start
// "2[abc]3[cd]ef"\n
// @lcpr case=end

// @lcpr case=start
// "abc3[cd]xyz"\n
// @lcpr case=end

 */

